#include"SList.h"

//int mainl ()
//{
//	SLNode* phead;
//	SLInit(&phead);
//
//	SLPushBack(&phead, 1);
//	SLPushBack(&phead, 2);
//	SLPushBack(&phead, 3);
//	SLPushBack(&phead, 4);
//	SLPushBack(&phead, 5);
//	SLPushBack(&phead, 6);
//	SLPrint(phead);//1->2->3->4->5->6->NULL
//
//	SLErase(&phead, SLFind(&phead, 1));
//	SLPrint(phead);//2->3->4->5->6->NULL
//	SLErase(&phead, SLFind(&phead, 6));
//	SLPrint(phead);//2->3->4->5->NULL
//
//	SLEraseAfter(&phead, SLFind(&phead, 5));
//	SLPrint(phead);//2->3->4->5->NULL
//	SLEraseAfter(&phead, SLFind(&phead, 2));
//	SLPrint(phead);//3->4->5->NULL
//
//	return 0;
//}

//#include"SList.h"
//int main()
//{
//	SLNode* phead;
//	SLInit(&phead);
//
//	SLPushBack(&phead, 2);
//	SLPushBack(&phead, 3);
//	SLPrint(phead);//2->3->NULL
//
//	SLPushFront(&phead, 1);
//	SLPushFront(&phead, 0);
//	SLPrint(phead);//0->1->2->3->NULL
//
//	SLPopBack(&phead);
//	SLPrint(phead);//0->1->2->NULL
//
//	SLPopFront(&phead);
//	SLPrint(phead);//1->2->NULL
//
//	return 0;
//}
//

//
//#include"SList.h"
//
//int main()
//{
//	SLNode* phead;
//	SLInit(&phead);
//
//	SLPushBack(&phead, 1);
//	SLPushBack(&phead, 2);
//	SLPushBack(&phead, 3);
//	SLPrint(phead);//1->2->3->NULL
//
//	SLInsert(&phead, SLFind(&phead, 1), 0);
//	SLPrint(phead);//0->1->2->3->NULL
//	SLInsert(&phead, SLFind(&phead, 3), 4);
//	SLPrint(phead);//0->1->2->4->3->NULL
//
//	SLInsertAfter(SLFind(&phead, 1), 9);
//	SLPrint(phead);//0->1->9->2->4->3->NULL
//	SLInsertAfter(SLFind(&phead, 3), 5);
//	SLPrint(phead);//0->1->9->2->4->3->5->NULL
//
//	return 0;
//}

//struct ListNode* sortList(struct ListNode* head)
//{
//    if (!head)
//        return NULL;
//    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
//    phead->next = NULL;
//    struct ListNode* prev = head, * pcur = head, * ret=NULL;
//
//    while (pcur)
//    {
//        int count = 0;
//        pcur = pcur->next;
//        if (!phead->next)
//        {
//            phead->next = prev;
//            ret = phead;
//            ret->next->next = NULL;
//        }
//        else
//        {
//            struct ListNode* cur = ret;
//            while (cur->next)
//            {
//                if (prev->val <= cur->next->val)
//                {
//                    
//                    prev->next = cur->next;
//                    cur->next = prev;
//                    break;
//                }
//                cur = cur->next;
//
//            }
//            if (!cur->next)
//            {
//                cur->next = prev;
//                prev->next = NULL;
//            }
//
//        }
//
//        prev = pcur;
//    }
//    return phead->next;
//}

struct ListNode* FindSLMid(struct ListNode* head)
{
    struct ListNode* mid = head, * fast = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        mid = mid->next;
    }
    return mid;
}

struct ListNode* reversal(struct ListNode* head)
{
    if (!head)
        return NULL;
    struct ListNode* pcur = head, * tail = head;
    struct ListNode* prev = head;
    tail = tail->next;
    head->next = NULL;
    while (tail)
    {
        pcur = tail;
        tail = tail->next;
        pcur->next = prev;
        prev = pcur;


    }

    return prev;
}


bool isPalindrome(struct ListNode* head)
{
    if (!head)
        return NULL;
    struct ListNode* mid = FindSLMid(head);
    struct ListNode* last = reversal(mid);

    while (last)
    {
        if (last->val != head->val)
        {
            return 0;
        }
        last = last->next;
        head = head->next;
    }


    return 1;
}


void test()
{
    struct ListNode* s;
    SLInit(&s);
    SLPushBack(&s, 1);
    SLPushBack(&s, 2);
    SLPushBack(&s, 2);
    SLPushBack(&s, 1);
    printf("%d\n", isPalindrome(s));

}

int main()
{
	test();
	return 0;
}